package com.dataStructure.并查集;

/**
 * 在Union的过程中，可能会出现树不平衡的情况，甚至退化成链表
 *
 * 有2种常见的优化方案
 *  1.基于size的优化：元素少的树 嫁接到 元素多的树
 *      基于size的优化，也可能会存在树不平衡的问题
 *  2.基于rank的优化：矮的树 嫁接到 高的树
 */
@SuppressWarnings("all")
public class 并查集_QuickUnion_Size优化 extends 并查集{
    private int [] sizes;

    public 并查集_QuickUnion_Size优化(int capacity) {
        super(capacity);

        //初始化每棵树的size
        sizes = new int[capacity];
        for (int i = 0; i < sizes.length; i++) {
            sizes[i] = 1;
        }
    }

    @Override
    public int find(int v) {
        rangCheck(v);
        //通过parent链条不断向上找
        //一直向上找到根节点为止
        while (v != parents[v]){
            v = parents[v];
        }
        return v;
    }

    @Override
    public void union(int v1, int v2) {

        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;

        //比较size，将元素少的树嫁接到元素多的树
        if (sizes[p1] < sizes[p2]){
            parents[p1] = p2;
            sizes[p2] += sizes[p1];
        }else {
            parents[p2] = p1;
            sizes[p1] += sizes[p2];
        }

    }
}
